/**
 * 堆
 */
;(function(window){


	var TNode = function(data){
		return {
			data: data,
			lChild: null,
			rChild: null
		}
	};

	var Heap = function(){
		this._heapArr = [];
		this._length = 0;
	};
	Heap.prototype = {
		constructor: Heap,
		_trickleUp: function(idx){
			var pIdx = Math.floor((idx-1)/2);
			var bottomNode = this._heapArr[idx];
			while(idx > 0 && this._heapArr[pIdx] < bottomNode){
				this._heapArr[idx] = this._heapArr[pIdx];
				idx = pIdx;
				pIdx = Math.floor((pIdx-1)/2);
			}
			this._heapArr[idx] = bottomNode;
		},
		_trickleDown: function(idx){
			var largerIdx;
			var topNode = this._heapArr[idx];
			while(idx < Math.floor(this._length/2)){
				var lIdx = 2*idx+1;
				var rIdx = lIdx+1;
				if(rIdx < this._length && this._heapArr[lIdx] < this._heapArr[rIdx]){
					largerIdx = rIdx;
				}else{
					largerIdx = lIdx;
				}
				if(topNode >= this._heapArr[largerIdx]){
					break;
				}
				this._heapArr[idx] = this._heapArr[largerIdx];
				idx = largerIdx;
			}
			this._heapArr[idx] = topNode;
		},
		insert: function(data){
			this._heapArr[this._length] = data;
			this._trickleUp(this._length++);
		},
		deleteNode: function(){
			var rootNode = this._heapArr[0];
			this._heapArr[0] = this._heapArr[--this._length];
			this._trickleDown(0);
			delete this._heapArr[this._length]; // 必须把数组的最后一个元素清除
			return rootNode;
		},
		change: function(idx, newValue){
			if( idx<0 || idx>this._length ) return false;
			var oldValue = this._heapArr[idx];
			this._heapArr[idx].data = newValue;
			if( oldValue < newValue )
				this._trickleDown(idx);
			else this._trickleUp(idx);
			return true;
		},
		/**
		 * 将堆数组转换为树型结构
		 * @return {TNode}
		 */
		convertToTree: function(){
			if( this._length == 0 ) return null;
			var treeArr = [];
			var root = null;
			for(var i=0;i<this._length;i++){
				treeArr[i] = TNode(this._heapArr[i]);
			}
			for(var j=0;j<this._length;j++){
				if( j==0 ) root = treeArr[0];
				var lIdx = 2*j+ 1, rIdx = lIdx+1;
				if( lIdx<this._length )treeArr[j].lChild = treeArr[lIdx];
				if( rIdx<this._length )treeArr[j].rChild = treeArr[rIdx];
			}
			return root;
		}
	};

	window.Heap = Heap;
})(window);